%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graphbook/
%%
%% Copyright (C) 2012 David Joyner <wdjoyner@gmail.com>
%% Copyright (C) 2009--2012 Minh Van Nguyen <mvngu.name@gmail.com>
%% Copyright (C) 2010 Nathann Cohen <nathann.cohen@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Graph coloring}
\label{chap:graph_coloring}

\begin{quote}
\includegraphics[scale=1.0]{image/graph-coloring/four-color-conjecture-qed} \\
\noindent
--- Spiked Math,
\url{http://spikedmath.com/210.html}
\end{quote}

\begin{itemize}
\item See Jensen and Toft~\cite{JensenToft1995} for a survey of graph
  coloring problems.

\item See Dyer and Frieze~\cite{DyerFrieze2010} for an algorithm on
  randomly colouring random graphs.
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Graph coloring problems originated with the coloring of maps.
For example, regard each state in the United States as a vertex,
and connect two vertices by an edge if and only if they share
a boundary, i.e., are neighbors. If you can color the United States
map using $k$ colors in such a way that no two neighboring states have the
same color then we say the map has a $k$-coloring.
While a student in London in the mid-1800's, the South African mathematician
Francis Guthrie conjectured to his mathematics professor
Augustus de Morgan that four colors suffice to color any map.
It was an open problem for over 100 years (only proven by Appel
and Haken in 1976).


\section{Vertex coloring}

When used without any qualification, a {\it coloring} of an
undirected graph $G=(V,E)$ is intended
to mean a vertex coloring, namely a labelling of the graph's
vertices with colors such that no two vertices sharing an
edge have the same color.

A coloring using at most $k$ colors is called a (proper) {\it $k$-coloring}.
\index{$k$-coloring}
For example, the $2$-colorable graphs are exactly the bipartite graphs.

\begin{remark}
For each $k=3,4,\dots$, the corresponding decision problem of deciding
if a given graph can be $k$-colored is NP-hard
(see \cite{JaegerEtAl1990}).
\end{remark}

The smallest number of colors needed to color a graph G is called
its (vertex) {\it chromatic number}, and is here denoted $\chi_v(G)$.
\index{chromatic!number}
\index{$\chi_v(G)$}
A subset of $V$ assigned to the same color is called a {\it color-class}.
A subset $S$ of $V$ is called an {\it independent set} if no two vertices
in $S$ are adjacent in $G$. By definition, every color-class forms
an independent set. The set of $t$-colorings is in one-to-one
correspondence with the partitions of $V$ into $t$ independent sets.
\index{color-class}
\index{independent set}

\begin{example}
\label{example:graph_coloring:dyck_graph_example}
\rm
The Dyck graph, shown in
Figure~\ref{fig:graph_coloring:dyck_graph_example}, is named after
Walther von Dyck.  It is a 3-regular graph with 32 vertices and 48
edges.  The graph is Hamiltonian with 120 distinct Hamiltonian cycles.
It has chromatic number 2~(in other words, is bipartite), chromatic
index 3, radius 5, diameter 5 and girth 6.  It is also a
3-vertex-connected and a 3-edge-connected graph.\qed
\end{example}

\begin{lstlisting}
sage: G = graphs.LCFGraph(32, [5,-5,13,-13], 8)
sage: G.is_bipartite()
True
sage: G.coloring()
[[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31],
 [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30]]
sage: G.is_vertex_transitive()
True
\end{lstlisting}

\begin{figure}[!htbp]
\centering
\index{graph!Dyck}
\includegraphics{image/graph-coloring/dyck-graph-example}
\caption{A Dyck graph example.}
\label{fig:graph_coloring:dyck_graph_example}
\end{figure}

A {\it clique} in $G$ is a subset of the vertex set $S \subset V$, such that
for every two vertices in $S$, there exists an edge connecting the two.
The {\it clique number} $\omega (G)$ of a graph $G$ is the number of vertices
in a maximal clique (a clique which cannot be extended to a clique of
larger size
by adding a vertex to it) in $G$.
\index{clique}
\index{clique!number}
\index{clique!maximal}
\index{$\omega(G)$}
From the definitions, we see that
the chromatic number is at least the clique number:

\[
    \chi_v(G) \ge \omega(G).
\]

It is also not hard to give a non-trivial upper bound.

\begin{theorem}
Every simple graph can be colored with one more color than the
maximum vertex degree,

\[
    \chi_v(G) \le \Delta(G) + 1.
\]
\end{theorem}

We give two proofs.

\begin{proof}
(proof 1)
We prove this by induction on the number $n$ of vertices.

It is obvious in the case $n=1$.

Assume the result is true for all graphs with $k-1$ vertices and let
$G=(V,E)$ be a graph with $k$ vertices. We want to chow that $G$ has a
coloring with $1+\Delta(G)$ colors. Let $v\in V$ and consider the
graph $G-v$. By hypothesis, this graph has a coloring with
$1+\Delta(G-v)$ colors. Since there are at most $\Delta(G)$
neighbors of $v$, no more than $\Delta(G)$ colors could be used for
these adjacent vertices. There are two cases.

Case $1+\Delta(G-v) < 1+\Delta(G)$. In this case, we create a new
color for $v$ to obtain a coloring for $G$ with
$2+\Delta(G-v) \leq 1+\Delta(G)$ colors.

Case $1+\Delta(G-v) = 1+\Delta(G)$. In this case, the vertices adjacent to
$v$ have been colored with at most $\Delta(G)$ colors, leaving us with
at least one unused color. We can use that color for $v$.
\end{proof}

\begin{proof}
(proof 2)
The fact that the graph coloring (decision) problem
is NP-complete must not prevent one from trying to
color it greedily. One such
method would be to iteratively pick, in a graph $G$, an uncolored
vertex $v$, and to color it with the smallest color available which
is not yet used by one of its neighbors.
Such a coloring algorithm will never
use more than $\Delta(G)+1$ different
colors (where $\Delta(G)$ is the maximal degree of $G$), as
no vertex in the procedure will ever exclude more than
$\Delta(G)$ colors.
\end{proof}

Such a greedy algorithm can be written in Sage in a few lines:

\begin{lstlisting}
sage: g = graphs.RandomGNP(100,5/100)
sage: C = Set(xrange(100))
sage: color = {}
sage: for u in g:
...      interdits = Set([color[v] for v in g.neighbors(u) if color.has_key(v)])
...      color[u] = min(C-interdits)
\end{lstlisting}


\begin{example}
\label{eg:graph_coloring:frucht_graph_vertex_coloring_example}
\rm
A Frucht graph, shown in
Figure~\ref{fig:graph_coloring:frucht_graph_vertex_coloring_example},
has 12 nodes and 18 edges.  It is $3$-regular, planar and Hamiltonian.
It is named after Robert Frucht.  The Frucht graph has no nontrivial
symmetries.  It has chromatic number 3, chromatic index 3, radius 3,
diameter 4 and girth 3.  It is 3-vertex-connected and 3-edge-connected
graph.\qed
\end{example}

\begin{lstlisting}
sage: G = graphs.FruchtGraph()
sage: G.show(dpi=300)
sage: vc = G.coloring()
sage: G.chromatic_number()
3
sage: d = {'blue':vc[0], 'red':vc[1], 'green':vc[2]}
sage: G.show(vertex_colors=d)
sage: G.automorphism_group().order()
1
\end{lstlisting}

\begin{figure}[!htbp]
\centering
\index{graph!Frucht}
\includegraphics{image/graph-coloring/frucht-graph-vertex-coloring-example}
\caption{Frucht graph vertex-coloring example.}
\label{fig:graph_coloring:frucht_graph_vertex_coloring_example}
\end{figure}

\begin{itemize}
\item Brook's Theorem
\item heuristics for vertex coloring
\end{itemize}

\begin{theorem}
(Brooks' inequality)
If $G$ is not a complete graph and is not an odd cycle graph then

\[
    \chi_v(G) \le \Delta(G).
\]
\end{theorem}
\index{Brooks' inequality}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Edge coloring}

Edge coloring is the direct application of vertex coloring to the
line graph of a graph $G$. (Recall, $L(G)$ is the graph whose
vertices are the edges of $G$, two vertices being adjacent if and
only if their corresponding edges share an endpoint).
We write $\chi_v(L(G)) = \chi_e(G)$ for the {\it chromatic index} of $G$.
(This is also called the {\it edge chromatic number}.
\index{chromatic!index}
\index{edge chromatic number}
An {\it edge coloring} of a graph is an assignment of colors to
edges so that no vertex is
incident to two edges of the same color. An edge coloring with
$k$ colors is called a {\it $k$-edge-coloring}.
\index{edge coloring}

\begin{example}
\label{eg:graph_coloring:heawood_graph_example}
\rm
The Heawood graph,\index{Heawood graph} shown in
Figure~\ref{fig:graph_coloring:heawood_graph_vertex_coloring_example},
is named after Percy John Heawood.  It is an undirected graph with
$14$ vertices and $21$ edges.  It is a $3$-regular,
distance-transitive, distance-regular graph.  It has chromatic number
$2$ and chromatic index $3$.  An edge-coloring is shown in
Figure~\ref{fig:graph_coloring:heawood_graph_edge_coloring_example}.
A vertex-coloring is shown in
Figure~\ref{fig:graph_coloring:heawood_graph_vertex_coloring_example}.

Recall that a graph is vertex-transitive if its automorphism group
acts transitively upon its vertices.  The automorphism group of the
Heawood graph is isomorphic to the projective linear group $\PGL2(7)$,
a group of order $336$.  It acts transitively on the vertices and on
the edges of the graph.  Therefore, this graph is
vertex-transitive.\qed
\end{example}

\begin{lstlisting}
sage: G = graphs.HeawoodGraph()
sage: ec = edge_coloring(G)
sage: d = {'blue':ec[0], 'green':ec[1], 'red':ec[2]}
sage: G.show(edge_colors = d)
sage: G.line_graph().chromatic_number()  # chromatic index
3
\end{lstlisting}

\begin{figure}[!htbp]
\centering
\includegraphics[scale=0.7]{image/graph-coloring/heawood-graph-edge-coloring-example}
\caption{The Heawood graph and an edge-coloring example.}
\label{fig:graph_coloring:heawood_graph_edge_coloring_example}
\end{figure}

\begin{lstlisting}
sage: G = graphs.HeawoodGraph()
sage: vc = G.coloring()
sage: vc
[[1, 3, 5, 7, 9, 11, 13], [0, 2, 4, 6, 8, 10, 12]]
sage: d = {'blue':vc[0], 'red':vc[1]}
sage: G.show(vertex_colors = d)
sage: G.chromatic_number()
2
\end{lstlisting}

\begin{figure}[!htbp]
\centering
\index{graph!Heawood}
\includegraphics[scale=0.7]{image/graph-coloring/heawood-graph-vertex-coloring-example}
\caption{The Heawood graph and an vertex-coloring example.}
\label{fig:graph_coloring:heawood_graph_vertex_coloring_example}
\end{figure}

\begin{example}
\label{eg:graph_coloring:icosahedral_graph_vertex_coloring_example}
\rm
The Icosahedral graph, shown in
Figure~\ref{fig:graph_coloring:icosahedral_graph_vertex_coloring_example},
is a particular projection of the edges of the solid icosahedron onto
the plane.  It is a $4$-regular graph with $30$ edges and $12$
vertices.  It has chromatic number $4$ and chromatic index $5$.  An
edge-coloring is shown in
Figure~\ref{fig:graph_coloring:icosahedral_graph_edge_coloring_example}.
A vertex-coloring is shown in
Figure~\ref{fig:graph_coloring:icosahedral_graph_vertex_coloring_example}.\qed
\end{example}

\begin{lstlisting}
sage: G = graphs.IcosahedralGraph()
sage: G.chromatic_number()
4
sage: vc = G.coloring()
sage: d = {'blue':vc[0], 'red':vc[1], 'green':vc[2],'orange':vc[3]}
sage: G.show(vertex_colors = d)
\end{lstlisting}

\begin{figure}[!htbp]
\centering
\includegraphics[scale=0.7]{image/graph-coloring/icosahedral-graph-vertex-coloring-example}
\caption{An icosahedral graph vertex-coloring example.}
\label{fig:graph_coloring:icosahedral_graph_vertex_coloring_example}
\end{figure}

\begin{lstlisting}
sage: G.is_hamiltonian()
True
sage: G.is_regular()
True
sage: G.is_vertex_transitive()
True
sage: G.is_perfect()
False
sage: G.is_planar()
True
sage: G.is_clique()
False
sage: G.is_bipartite()
False
\end{lstlisting}

\begin{lstlisting}
sage: G.line_graph().chromatic_number()
5
sage: ec = edge_coloring(G)
sage: d = {'blue':ec[0], 'red':ec[1], 'green':ec[2],'orange':ec[3],'yellow':ec[4]}
sage: G.show(edge_colors = d)
\end{lstlisting}

\begin{figure}[!htbp]
\centering
\index{graph!icosahedral}
\includegraphics[scale=0.7]{image/graph-coloring/icosahedral-graph-edge-coloring-example}
\caption{An icosahedral graph edge-coloring example.}
\label{fig:graph_coloring:icosahedral_graph_edge_coloring_example}
\end{figure}

As in the case of vertex-coloring, the edge-coloring decision problem is
still NP-complete. However, it is much better understood through
Vizing's theorem.

\begin{theorem}
(Vizing's theorem)
The edges of a graph $G$ can be properly colored using at least
$\Delta(G)$ colors and at most $\Delta(G)+1$,

\[
\Delta(G)\leq \chi_e(G)\leq \Delta(G)+1.
\]
\end{theorem}
\index{Vizing's theorem}

Notice that the lower bound can be easily proved : if a vertex
$v$ has a degree $d(v)$, then at least $d(v)$ colors are required
to color $G$ as all the edges incident to $v$ must receive
different colors.

Note the upper bound of $\Delta(G)+1$
cannot be deduced from the greedy algorithm given in the
previous section, as the maximal degree of the line graph
$L(G)$ is not equal to
$\Delta(G)$ but to $\displaystyle \max_{u\sim v}d(u)+d(v)-2$, which
can reach $2\Delta(G)-2$ in regular graphs.


\begin{example}
\label{eg:graph_coloring:pappas_graph_edge_coloring_example}
\rm
The Pappus graph, shown in
Figure~\ref{fig:graph_coloring:pappas_graph_edge_coloring_example}, is
named after Pappus of Alexandria.  It is $3$-regular, symmetric, and
distance-regular with 18 vertices and 27 edges.  The Pappus graph has
girth 6, diameter 4, radius 4, chromatic number 2~(i.e.~is bipartite),
chromatic index 3 and is both 3-vertex-connected and
3-edge-connected.\qed
\end{example}

\begin{lstlisting}
sage: G = graphs.PappusGraph()
sage: G.coloring()
[[1, 3, 5, 6, 8, 10, 12, 14, 16], [0, 2, 4, 7, 9, 11, 13, 15, 17]]
sage: G.is_regular()
True
sage: G.is_planar()
False
sage: G.is_vertex_transitive()
True
sage: G.is_hamiltonian()
True
sage: G.girth()
6
sage: G.is_bipartite()
True
sage: G.show(dpi=300)
sage: G.line_graph().chromatic_number()
3
sage: ec = edge_coloring(G)
sage: ec
[[(0, 1), (2, 3), (4, 5), (6, 17), (7, 14), (8, 13), (9, 16), (10, 15), (11, 12)],
 [(0, 5), (1, 2), (3, 4), (6, 13), (7, 12), (8, 15), (9, 14), (10, 17), (11, 16)],
 [(0, 6), (1, 7), (2, 8), (3, 9), (4, 10), (5, 11), (12, 15), (13, 16), (14, 17)]]
sage: d = {'blue':ec[0], 'red':ec[1], 'green':ec[2]}
sage: G.plot(edge_colors = d).show()
\end{lstlisting}

\begin{figure}[!htbp]
\centering
\index{graph!Pappas}
\includegraphics[scale=0.7]{image/graph-coloring/pappas-graph-edge-coloring-example}
\caption{A Pappas graph edge-coloring example.}
\label{fig:graph_coloring:pappas_graph_edge_coloring_example}
\end{figure}

\begin{itemize}
\item algorithm for edge coloring by maximum matching
\item algorithm for sequential edge coloring
\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{The chromatic polynomial}

George David Birkhoff introduced the chromatic polynomial in 1912.
The chromatic polynomial is defined as the unique interpolating
polynomial of degree $n$ through the points $(k,P_G(k))$ for
$k=0,1,\dots n$, where $n$ is the number of vertices in $G$.
For natural numbers $t$, the chromatic polynomial is the function
that counts the
number of $t$-colorings of $G$.

As the name indicates, for a given $G$ the function is indeed a
polynomial in $t$.

For a complex number $x$, let $x_{(k)}=\prod_{i=0}^{k-1} (x-i)$.

\begin{lemma}
If $m_k(G)$ denotes the number of distinct partitions of $V$
into $k$ different color-classes then

\[
P_G(t) = \sum_{k=1}^n m_k(G)t_{(k)}.
\]
\end{lemma}

\index{chromatic!polynomial}

\begin{proof}
Given a partition of $V$ into $k$ color-classes, we can assign
$t$ colors to the color-classes in $t(t-1)\dots (t-k+1)=t_{(k)}$ ways.
For each $k$ with $1\leq k\leq n$, there are
$m_k(G)$ distinct partitions of $V$ into $k$ such color-classes.
Therefore, the number of colorings with $t$ colors is
$ \sum_{k=1}^n m_k(G)t_{(k)},$ as desired.
\end{proof}



\begin{theorem}
A graph $G$ with $n$ vertices is a tree if and only if $P(G, t) =
t(t-1)^{n-1}$.
\end{theorem}

\begin{proof}
We prove this by induction on $n$. The statement is clearly
true when $n=1$.

Assume the statement holds for any tree of $n-1$ vertices
and let $G$ be a tree with $n$ vertices. There is a vertex $v$
of $G$ having degree $1$. The graph $G-v$ is a tree having $n-1$
vertices, so has $t(t-1)^{n-2}$ $t$-colorings. The number of
$t$-colorings of $G$ is the number of $t$-colorings of $G-v$ times the
number of ways to color $v$. Since we may color $v$ using any
color not used for its one neighbor, there are $t-1$ colorings of $v$.
Therefore, $G$ has $t(t-1)^{n-1}$ $t$-colorings.
\end{proof}

The theorem above gives examples of non-isomorphic graphs which have
the same chromatic polynomial.


Two graphs are said to be {\it chromatically equivalent} if they have the
same chromatic polynomial. For example, two trees having the same
number of vertices are chromatically equivalent.
\index{chromatically equivalent}

It is also an open problem to find necessary and sufficient conditions
for two arbitrary graphs to be chromatically equivalent.

\begin{theorem}
If G has $n$ vertices, $m$ edges, and $k$ components $G_1$,
$G_2$,\dots ,$G_k$, then

\[
P(G, t) = P(G_1, t)P(G_2,t) \cdots P(G_k,t).
\]
\end{theorem}

This is proven by induction on $k$ and the proof is left to the
interested reader.

Fix a pair of vertices $u, v\in V$.
Recall that the (edge contraction)
graph $G/uv$ is obtained by merging the two vertices and removing
any edges between them. Recall that the (edge deletion)
graph $G-uv$ is obtained by merging the the edge $uv$ but not the
two vertices $u,v$.

\begin{theorem}
(Fundamental Reduction Theorem)
The chromatic polynomial satisfies the recurrence relation

\[
    P(G,t) = P(G-uv, t) - P(G/uv,t) .
\]
\end{theorem}

For example, if $G$ is a tree then $ G/uv$ is another tree
but $ G-uv$ is a non-connected graph.

A root (or zero) of a chromatic polynomial, called a {\it chromatic root}
is a value $x$ where $P_G(x)=0$.
\index{chromatic!root}

\begin{theorem}
$\chi_v(C)$ is the smallest positive integer that is not a chromatic root:

\[
    \chi_v (G)=\min\{ k\,\ |\ P(G,k) > 0 \}.
\]
\end{theorem}

Birkhoff noted that one could establish the four color theorem by
showing $P(G,4)>0$ for all planar graphs $G$. This lead to the
following statement, which is still an open problem today.

\begin{conjecture}
(Birkhoff-Lewis Conjecture)
As a function of a real variable $t$, $P(g,t)$ is zero-free in the
interval $t\geq 4$.
\end{conjecture}
\index{Birkhoff-Lewis Conjecture}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Applications of graph coloring}

\begin{itemize}
\item assignment problems

\item scheduling problems

\item matching problems

\item map coloring and the Four Color Problem
\end{itemize}


\subsection{Application to scheduling}

Assume that we have a finite set of different people (for example, students)
and a finite set of distinct one-hour meetings they could attend (for example,
classes). Construct the
graph $G$ as follows. The vertices $V$ of $G$ are given by the set of
meetings. We connect two meetings with an edge if some person
needs to attend both meetings.

\begin{example}
\label{eg:coloring}
\rm
Suppose the $\times$ in the table below indicated that the student in
that column is attending the class in that row.

\begin{center}
\begin{tabular}{c|cccc}
          & Bob      & Carol    & Ted      & Zoe      \\\hline
Calculus  &          & $\times$ & $\times$ &          \\
Chemistry & $\times$ & $\times$ & $\times$ & $\times$ \\
English   & $\times$ & $\times$ & $\times$ & $\times$ \\
History   & $\times$ &          &          & $\times$ \\
Physics   &          & $\times$ & $\times$ &          \\\hline
\end{tabular}
\end{center}
%%
Let $0 = \text{Calculus}$, $1 = \text{Chemistry}$,
$2 = \text{English}$, $3 = \text{History}$, and $4 = \text{Physics}$.
Then the corresponding graph can be constructed and drawn in Sage
using the following commands~(see
Figure~\ref{fig:graph_coloring:scheduling}).\qed
\end{example}

\begin{lstlisting}
sage: G = Graph({0:[1,2,4], 1:[2,3,4], 2:[3,4]})
sage: G.show()
sage: G.coloring()
[[2], [4], [0, 3], [1]]
\end{lstlisting}

\begin{figure}[h!]
\begin{center}
\includegraphics[height=4cm,width=5cm]{image/graph-coloring/graph-coloring-scheduling}
\end{center}
\caption{An application of graph coloring to scheduling.}
\label{fig:graph_coloring:scheduling}
\end{figure}

\begin{theorem}
The minimum number of hours required for the schedule of meetings in
our scheduling problem is $\chi_v(G)$.
\end{theorem}

\begin{proof}

Suppose we can schedule the meetings in $k$ hours. In other words,
each person attends the meetings they need to and they
can do so in at most $k$ kours. Order the meeting
times $1$, $2$, \dots, $k$. Each meeting must occur in one and only
one of these time slots (although a given time slot may have
several meetings). We color the graph $G$ as follows:
if a meeting occurs in hour $i$ then use color $i$ for all the
meetings that meet at that hour. Consider two adjacent
vertices. These vertices correspond to two meetings which
share one or more people. Since a person cannot be in two places at
the same time, these two meetings by have different meeting times,
hence the vertices must have different colors. This implies
$\chi_v(G)\leq k$.

Conversely, suppose that $G$ has a $k$-coloring.
The meetings with color $i$ (where $1\leq i\leq k$)
can be held at the same time since any two such meetings
correspond to non-adjacnt vertices, hence have no
person in common. Therefore, the minimum number of
hours requires for the meeting schedule is less than
or equal to $\chi_v(G)$.
\end{proof}

\begin{problem}
\item
What is the number of hours required for a schedule
in Example~\ref{eg:coloring}?
% Ans: 4
\item
Draw the Dyck graph in Example \ref{example:graph_coloring:dyck_graph_example}
as a bipartite graph.

\item
Draw the Pappas graph in Example
\ref{eg:graph_coloring:pappas_graph_edge_coloring_example}
as a bipartite graph.
\end{problem}

\subsection{Map coloring}


\begin{theorem}
(Four Color Theorem)
Every planar graph can be $4$-colored.
\end{theorem}
